#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class info{
public:
    //返回信息中必须有左子树的最小节点和最大节点及右子树的最小节点
    info(bool status,Node* head,Node* end){
        this->status = status;
        this->head = head;
        this->end = end;
    }
public:
    bool status; //判断是否是空链表
    Node* head;
    Node* end;
};


class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root==NULL){
            return NULL;
        }
        return func(root).head;

    }
    info func(Node* root){
        if(root==NULL){
            return info(false,NULL,NULL);
        }
        info infoLeft = func(root->left);
        info infoRight = func(root->right);
        if(infoLeft.status!=false&&infoRight.status!=false){
            infoLeft.end->right = root;
            root->left = infoLeft.end;
            root->right = infoRight.head;
            infoRight.head->left = root;
            infoLeft.head->left = infoRight.end;
            infoRight.end->right = infoLeft.head;
            return info(true,infoLeft.head,infoRight.end);
        }
        else if(infoLeft.status==false&&infoRight.status!=false){
            root->right = infoRight.head;
            infoRight.head->left = root;
            root->left = infoRight.end;
            infoRight.end->right = root;
            return info(true,root,infoRight.end);
        }
        else if(infoLeft.status!=false&&infoRight.status==false){
            infoLeft.end->right = root;
            root->left = infoLeft.end;
            infoLeft.head->left = root;
            root->right = infoLeft.head;
            return info(true,infoLeft.head,root);
        }
        else{
            root->left = root;
            root->right  = root;
            return info(true,root,root);
        }
    }
};  


int main(){
    Node* head = new Node(4);
    head->left = new Node(2);
    head->right = new Node(5);
    head->left->left = new Node(1);
    head->left->right = new Node(3);
    Solution S;
    Node* T = S.treeToDoublyList(head); 
    return 0;
}